﻿//#include<stdio.h>
//#include<assert.h>
//unsigned int my_strlen(char* str)
//{
//	assert(str);
//	int count = 0;
//	while (*str++)
//	{
//		count++;
//	}
//	return count;
//}
//char* my_strcpy(char* dest, const char* src)
//{
//	assert(dest && src);
//	char* ret = dest;
//	while (*dest++ = *src++)
//		;
//	return ret;
//}
//char* strcat(char* dest,const char* src)
//{
//	assert(dest && src);
//	char* ret=dest;
//	while (*dest)
//	{
//		dest++;
//	}
//	while (*dest++ = *src++)
//		;
//	return ret;
//}
//int my_strcmp(const char* str1, const char* str2)
//{
//	assert(str1 && str2);
//	while (*str1 == *str2)
//	{
//		if (*str1 == '\0')
//			return 0;
//		str1++;
//		str2++;
//	}
//	return *str1 - *str2;
//}
//char* my_strstr(const char* str1, const char* str2)
//{
//	assert(str1 && str2);
//	char* cur = str1;
//	char*s2 = str2;
//	while (*cur)
//	{
//		str1 = cur;
//		str2 = s2;
//		while (*str1&&*str2&&*str1== *str2)
//		{
//			str1++;
//			str2++;
//		}
//		if (*str2 == '\0')
//			return cur;
//		else if (*str1 == '\0')
//			return NULL;
//		cur++;
//	}
//}
//int main()
//{
//	char* str1 = "";
//	char* str2 = "";
//	printf("%s", my_strstr(str1, str2));
//}
//----------------------------------------------------KMP
#include<stdio.h>
#include<string.h>
#include<assert.h>
void GetNext(int* next, char*sub)
{
	int lensub = strlen(sub);
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int k = 0;
	while (i < lensub)
	{
		if ((k==-1)||sub[k] == sub[i - 1])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}
int kmp(char* str, char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	int* next = (int*)malloc(sizeof(int) * lensub);
	GetNext(next, sub);
	int j = 0;
	int i = pos;
	if (pos < 0 || pos >= lenstr)return-1;
	while (i < lenstr && j < lensub)
	{
		if ((j==-1)||str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	free(next);
	if (j == lensub)
		return i - j;
	else
		return -1;


}
char* my_strstr(char* str, char* sub)
{
	assert(str != NULL && sub != NULL);
	char* sub_begin = sub;
	char* cur = str;
	while (*str && *sub)
	{
		if (*str == *sub)
		{
			str++;
			sub++;
		}
		else
		{
			cur++;
			sub = sub_begin;
			str = cur;
		}


	}
	if (*sub == '\0')
		return cur;
	return -1;
}
int main()
{
	char* str1 = "ababcaab";
	char* str2 = "abcaab";
	printf("%d\n", kmp(str1, str2, 1));
	printf("%s\n", my_strstr(str1, str2));
}